#include <iostream>
#include <sstream>
using std::cout;
using std::ostream;

template <class T>
class BSTree
{
public:
    class Node
    {
    private:
        T value;
        Node* left;
        Node* right;
    public:
        Node( T n_val) : value( n_val)
        {
            left = NULL;
            right = NULL;
        }
        ~Node( )
        {
            if ( left )
                delete left;
            if ( right )
                delete right;
        }
        void addNode( T n_val);
        void printBSTree( int num_of_sp, ostream &os);
        bool find( T key);
        void infixTraverce( ostream &os);
    };
    BSTree()
    {
        root = NULL;
    }
    ~BSTree()
    {
        if ( root )
        {
            delete root;
        }
    }
    void addNode( T n_val);
    void printBSTree( ostream &os);
    bool find( T key);
    void infixTraverce( ostream &os);
private:
    Node* root;
};
template <class T>
void BSTree<T>::addNode( T n_val)
{
    if ( !root )
    {
        root = new Node( n_val);
    } else
    {
        root->addNode( n_val);
    }
}

template <class T>
ostream &operator <<( ostream &os, BSTree<T> &tree)
{
    tree.printBSTree( os);
    return os;
}

template <class T>
void BSTree<T>::printBSTree( ostream &os)
{
    if ( root )
        root->printBSTree( 0, os);
    else
        os << "Tree is empty!\n";
}

template <class T>
bool BSTree<T>::find( T key)
{
    if ( root )
        return root->find( key);
    else
        return 0;
}

template <class T>
void BSTree<T>::infixTraverce( ostream &os)
{
    if ( root )
        root->infixTraverce( os);
    else
        os << "Tree is empty!\n";
}

template <class T>
void BSTree<T>::Node::addNode( T n_val)
{
    if ( n_val < value && left )
    {
        left->addNode( n_val);
    } else if ( n_val < value && !left )
    {
        left = new Node( n_val);
    } else if ( right )
    {
        right->addNode( n_val);
    } else
    {
        right = new Node( n_val);
    }
}

template <class T>
void BSTree<T>::Node::printBSTree( int num_of_sp, ostream &os)
{
    if ( left )
    {
        left->printBSTree( num_of_sp + 3, os);
    }
    for ( int i = 0; i < num_of_sp; i++ )
    {
        os << "  ";
    }
    os << value << "\n";
    if ( right )
    {
        right->printBSTree( num_of_sp + 3, os);
    }
}

template <class T>
bool BSTree<T>::Node::find( T key)
{
    if ( value == key )
    {
        return true;
    } else if ( key < value && left )
    {
        return left->find( key);
    } else if ( right )
    {
        return right->find( key);
    } else
    {
        return false;
    }
}

template <class T>
void BSTree<T>::Node::infixTraverce( ostream &os)
{
    if ( left )
    {
        left->infixTraverce( os);
    }
    os << value << "\n";
    if ( right )
    {
        right->infixTraverce( os);
    }
}
